# 给定 pushed 和 popped 两个序列，每个序列中的 值都不重复，只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时
# ，返回 true；否则，返回 false 。
#
#  示例 1：
# 输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
# 输出：true
# 解释：我们可以按以下顺序执行：
# push(1), push(2), push(3), push(4), pop() -> 4,
# push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
#
#  示例 2：
# 输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
# 输出：false
# 解释：1 不能在 2 之前弹出。
class Solution:
    """
    每次比较栈顶元素与弹出序列是否一致，一致则出栈
    细节: 建立一个辅助栈(用于保存压栈的顺序)
        循环向辅助栈中push压入序列的元素
        如果辅助栈中的栈顶元素与popped的当前元素不同，则继续将pushed中的元素压入辅助栈;
        如果它与当前弹出的元素相同，则继续弹出栈顶元素; 循环后检查辅助栈是否为空
    """
    def validateStackSequences(self, pushed, popped) -> bool:
        stack = []  # 保存压栈的顺序
        i = 0
        for num in pushed:
            stack.append(num)
            while len(stack) > 0 and stack[-1] == popped[i]:
                i += 1
                stack.pop()
        return len(stack) == 0


if __name__ == "__main__":
    # pushed = [1, 2, 3, 4, 5]
    # popped = [4, 5, 3, 2, 1]

    pushed = [1, 2, 3, 4, 5]
    popped = [4, 3, 5, 1, 2]
    print(Solution().validateStackSequences(pushed, popped))
